package com.sunny.l70;

import java.util.HashSet;
import java.util.Objects;
/**
 *  Given a 2D board and a word, find if the word exists in the grid.

 The word can be constructed from letters of sequentially adjacent cell,
 where "adjacent" cells are those horizontally or vertically neighboring.
 The same letter cell may not be used more than once.
 */

/**
 * @Author zsunny
 * @Date 2018/9/22 9:47
 * @Mail zsunny@yeah.net
 */
public class Solution {

    int[][] direct = {{1,0},{-1,0},{0,1},{0,-1}};

    HashSet<Point> used = new HashSet<>();

    public static void main(String[] args) {

        Solution solution = new Solution();
        char[][] board = {{'a','a'}};
        String word = "aaa";

        System.out.println(solution.exist(board, word));

    }

    public boolean exist(char[][] board, String word) {
        if(null == board || 0 == board.length){
            if(0 == word.length())
                return true;
            return false;
        }
        boolean res = false;
        for(int i=0;i<board.length;i++){
            for(int j=0;j<board[0].length;j++){
                if(board[i][j] == word.charAt(0)){
                    Point s = new Point(i, j);
                    used.clear();
//                    System.out.println(s);
                    used.add(s);
                    res = res || dfs(board, word, 1, s);
//                    System.out.println(res);
                    used.remove(s);
                }
            }
        }
        return res;
    }

    public boolean dfs(char[][] board, String word, int ind, Point cur){
//        System.out.println(word+" "+ind+" "+cur);
//        System.out.println(used);
        if(ind == word.length()){
            return true;
        }
        int n = board.length;
        int m = board[0].length;
        boolean exist = false;
        boolean res = false;
        for(int i=0;i<4;i++){
            Point tmp = new Point(cur.x+direct[i][0], cur.y+direct[i][1]);
//            System.out.println(tmp+" "+used+" "+used.contains(tmp));
            if(judge(tmp, n, m) && board[tmp.x][tmp.y] == word.charAt(ind) && !used.contains(tmp)){
                exist = true;
                used.add(tmp);
                res = res || dfs(board, word, ind+1, tmp);
                used.remove(tmp);
            }
        }
        if(!exist)
            return exist;
        return res;
    }

    public boolean judge(Point s, int n, int m){
        if(s.x < 0 || s.x >= n || s.y < 0 || s.y >= m)
            return false;
        return true;
    }
}

class Point{
    int x;
    int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Point point = (Point) o;
        return x == point.x &&
                y == point.y;
    }

    @Override
    public int hashCode() {

        return Objects.hash(x, y);
    }

    @Override
    public String toString() {
        return "Point{" +
                "x=" + x +
                ", y=" + y +
                '}';
    }
}
